using System;
using System.Collections;
using System.Text;

public class SudokuI6
{
    public int[] initialize(int N)
    {
        Init(N);
        InitSets();
        InitPairs();
        init();
        return new int[] { 1, 1 };
    }
    public int[] queryResults(int x, int[] qr)
    {
        pi = qi = -1;
        int i = qr[0] - 1, j = qr[1] - 1, k = i * N2 + j;
        x--;
        set(x, k);
        if (qn < N2)
        {
            extend(x, k);
            qr[1] = N * (qn % N) + (qn / N) + 1;
            qr[0] = ++qn;
            return qr;
        }
        update();
        return best();
    }
    bool done;
    void update()
    {
    Loop:
        pi++;
        extend(qx[pi], qk[pi]);
        if (pi < qi)
            goto Loop;
    Check:
        done = false;
        single(rcs, rsets);
        single(ccs, csets);
        single(acs, asets);
        if (pi < qi)
            goto Loop;
        if (done)
            goto Check;
        checkPairs();
        if (pi < qi)
            goto Loop;
        if (done)
            goto Check;
    }
    int qi, pi;
    int[] qx, qk, rs;
    bool[] rcs, ccs, acs;
    ulong[] pairsMask;
    bool[] pairsUpdating;
    ulong[] ms;
    void init()
    {
        pairsMask = new ulong[pairs.Length];
        pairsUpdating = new bool[pairs.Length];
        for (int i = pairsMask.Length - 1; i >= 0; i--)
            pairsMask[i] = MASK;
        rcs = new bool[N4];
        ccs = new bool[N4];
        acs = new bool[N4];
        ms = new ulong[N4];
        for (int i = N4 - 1; i >= 0; i--)
            ms[i] = MASK;

        rs = new int[N4];
        qi = -1;
        qx = new int[N4];
        qk = new int[N4];
    }

    void mask(ulong m, int k)
    {
        m = ms[k] & m;
        if (ms[k] == m)
            return;
        ms[k] = m;
        if (((m - 1) & m) == 0)
        {
            int x = GetX(m);
            rs[k] = x + 1;
            add(x, k);
        }
        notify(k);
        done = true;
    }
    void set(int x, int k)
    {
        if (rs[k] != 0)
            return;
        ms[k] = 1LU << x;
        rs[k] = x + 1;
        add(x, k);
        notify(k);
    }
    void notify(int k)
    {
        foreach (int index in pairsId[k])
            pairsUpdating[index] = true;
        int i = k / N2;
        k = k % N2;
        rcs[i] = true;
        ccs[k] = true;
        acs[i / N * N + k / N] = true;
    }
    void add(int x, int k)
    {
        qi++;
        qx[qi] = x;
        qk[qi] = k;
    }

    void extend(int x, int k)
    {
        int i = k / N2, j = k % N2;
        ulong m = MASK ^ (1LU << x);
        foreach (int index in asets[i / N * N + j / N])
            if (index != k)
                mask(m, index);
        foreach (int index in rsets[i])
            if (index != k)
                mask(m, index);
        foreach (int index in csets[j])
            if (index != k)
                mask(m, index);
    }

    void checkPairs()
    {
        for (int i = pairs.Length - 1; i >= 0; i--)
            if (pairsUpdating[i])
            {
                pairsUpdating[i] = false;
                ulong m = 0LU;
                foreach (int id in pairs[i])
                    m |= ms[id];
                if (pairsMask[i] != m)
                {
                    pairsMask[i] = m;
                    foreach (int id in pairs[i ^ 1])
                        mask(m, id);
                }
            }
    }

    void single(bool[] cs, int[][] sets)
    {
        ulong[] sms = new ulong[N2 + 1];
        for (int a = N2 - 1; a >= 0; a--)
            if (cs[a])
            {
                cs[a] = false;
                int[] list = sets[a];
                for (int i = N2 - 1; i >= 0; i--)
                    sms[i] = sms[i + 1] | ms[list[i]];
                ulong m = 0LU;
                for (int i = 0; i < N2; i++)
                {
                    if ((m | sms[i + 1]) != MASK)
                        mask((m | sms[i + 1]) ^ MASK, list[i]);
                    m |= ms[list[i]];
                }
            }
    }
    Random rand = new Random();
    int[] best()
    {
        double best = double.MinValue, tt;
        int bestk = -1, k;
        for (k = N4 - 1; k >= 0; k--)
            if (rs[k] == 0 && (tt = 3 * N * Count(ms[k]) + (k / N2) + (k % N2) + rand.NextDouble()) >= best)
            {
                best = tt; bestk = k;
            }
        if (best != double.MinValue)
            return new int[] { (bestk / N2) + 1, (bestk % N2) + 1 };
        return rs;
    }

    #region Statics
    static ulong MASK;
    static int N, N2, N3, N4, qn;
    static void Init(int n)
    {
        qn = 1;
        N = n;
        N2 = n * n;
        N3 = N2 * n;
        N4 = N3 * n;
        MASK = 1LU << (N2 - 1);
        MASK = (MASK - 1) + MASK;
    }
    #region sets
    static int[][] rsets, csets, asets;
    static void InitSets()
    {
        rsets = new int[N2][];
        csets = new int[N2][];
        asets = new int[N2][];
        for (int i = N2 - 1; i >= 0; i--)
        {
            rsets[i] = new int[N2];
            csets[i] = new int[N2];
            asets[i] = new int[N2];
        }
        for (int k = N4 - 1, i = N2 - 1; i >= 0; i--)
            for (int j = N2 - 1; j >= 0; j--, k--)
            {
                rsets[i][j] = k;
                csets[j][i] = k;
                asets[i / N * N + j / N][(i % N) * N + (j % N)] = k;
            }
    }
    #endregion

    #region pairs
    static int[][] pairs, pairsId;
    static void InitPairs()
    {
        pairs = new int[4 * N3][];
        int p = 0;
        for (int i = 0; i < N2; i++)
        {
            int a = i % N;
            int[] rset = rsets[i], cset = csets[i];
            for (int j = 0; j < N; j++)
            {
                int[] aset = asets[i / N * N + j],
                    p1 = new int[N2 - N], p2 = new int[N2 - N];
                Array.Copy(rset, 0, p1, 0, j * N);
                Array.Copy(rset, (j + 1) * N, p1, j * N, (N - j - 1) * N);
                Array.Copy(aset, 0, p2, 0, a * N);
                Array.Copy(aset, (a + 1) * N, p2, a * N, (N - a - 1) * N);
                pairs[p++] = p1; pairs[p++] = p2;
                p1 = new int[N2 - N]; p2 = new int[N2 - N];
                aset = asets[j * N + i / N];
                Array.Copy(cset, 0, p1, 0, j * N);
                Array.Copy(cset, (j + 1) * N, p1, j * N, (N - j - 1) * N);
                for (int k = 0, kk = 0; k < N2; k++)
                    if (k % N != a)
                        p2[kk++] = aset[k];
                pairs[p++] = p1; pairs[p++] = p2;
            }
        }
        pairsId = new int[N4][];
        for (int i = N4 - 1; i >= 0; i--)
            pairsId[i] = new int[4 * (N - 1)];
        int[] pairsIdi = new int[N4];
        for (int i = pairs.Length - 1; i >= 0; i--)
            foreach (int index in pairs[i])
                pairsId[index][pairsIdi[index]++] = i;
    }
    #endregion
    #endregion

    static int Count(ulong m)
    {
        int ret = 0;
        while (m > 0)
        {
            ret += (int)(m & 1UL);
            m >>= 1;
        }
        return ret;
    }
    static int GetX(ulong m)
    {
        for (int q = 0; q < N2; q++)
            if ((m & (1LU << q)) != 0LU)
                return q;
        return -1;
    }
}
